package cn.cxq.learning.graph;

import org.junit.jupiter.api.Test;

import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 本测试中的路径无任何意义，就是一些随机数
 */
public class Client {

    @Test
    public void testUndirectedGraph() {

        String[] vertexes = {"北京", "天津", "上海", "广州", "杭州", "武汉", "哈尔滨", "重庆", "成都"};

        int[][] edges = {{0, 1, 1}, {0, 2, 1}, {1, 2, 1}, {1, 3, 1}, {1, 4, 1}, {3, 4, 1}, {1, 5, 1}, {2, 6, 1}, {6, 7, 1}, {7, 8, 1}, {2, 8, 1}};

        UndirectedGraph undirectedGraph = new UndirectedGraph(vertexes, edges);

        System.out.println("邻接矩阵：");
        /**
         * 0 1 1 0 0
         * 1 0 1 1 0
         * 1 1 0 0 1
         * 0 1 0 0 0
         * 0 0 1 0 0
         */
        undirectedGraph.printAdjacencyMatrix();


        System.out.println("-------------------------------------------");

        System.out.println("深度优先遍历：");
        undirectedGraph.dfs(); //北京--->天津--->上海--->哈尔滨--->重庆--->成都--->广州--->杭州--->武汉--->

        System.out.println("\n-------------------------------------------");

        System.out.println("广度优先遍历：");
        undirectedGraph.bfs(); //北京--->天津--->上海--->广州--->杭州--->武汉--->哈尔滨--->成都--->重庆--->

    }

    @Test
    public void testPrim() {
        String[] vertexes = {"北京", "天津", "上海", "广州", "杭州", "武汉", "哈尔滨", "重庆", "成都"};

        int[][] edges = {{0, 1, 34}, {0, 2, 20}, {1, 2, 50}, {1, 3, 15},
                {1, 4, 50}, {2, 5, 50}, {3, 4, 40}, {4, 5, 20},
                {5, 7, 10}, {1, 5, 25}, {2, 6, 35}, {6, 7, 22},
                {7, 8, 11}, {2, 8, 6}};

        UndirectedGraph undirectedGraph = new UndirectedGraph(vertexes, edges);
        undirectedGraph.prim();
    }

    @Test
    public void testKruskal() {
        String[] vertexes = {"北京", "天津", "上海", "广州", "杭州", "武汉", "哈尔滨", "重庆", "成都"};

        int[][] edges = {{0, 1, 34}, {0, 2, 20}, {1, 2, 50}, {1, 3, 15},
                {1, 4, 50}, {2, 5, 50}, {3, 4, 40}, {4, 5, 20},
                {5, 7, 10}, {1, 5, 25}, {2, 6, 35}, {6, 7, 22},
                {7, 8, 11}, {2, 8, 6}};

        UndirectedGraph undirectedGraph = new UndirectedGraph(vertexes, edges);
        undirectedGraph.kruskal();
    }

    @Test
    public void testDijkstra() {
        String[] vertexes = {"北京", "天津", "上海", "广州", "杭州", "武汉", "哈尔滨", "重庆", "成都"};

        int[][] edges = {{0, 1, 34}, {0, 2, 20}, {1, 2, 5}, {1, 3, 15},
                {1, 4, 50}, {2, 5, 50}, {3, 4, 40}, {4, 5, 20},
                {5, 7, 10}, {1, 5, 25}, {2, 6, 35}, {6, 7, 22},
                {7, 8, 11}, {2, 8, 6}};

        UndirectedGraph undirectedGraph = new UndirectedGraph(vertexes, edges);


        for (int i = 0; i < vertexes.length; i++) {

            int[] shortest = undirectedGraph.dijkstra(i);

            System.out.println(vertexes[i] + "最短路径表：");

            for (int j = 0; j < shortest.length; j++) {
                System.out.print(shortest[j] + " ");
            }

            System.out.println();

            System.out.println("--------------------------------------------------------------");


            Map<Integer, List<int[]>> listMap = undirectedGraph.dijkstraForMap(i);
            printMap(i, listMap, vertexes);
        }

    }

    private void printMap(int index, Map<Integer, List<int[]>> listMap, String[] vertexes) {
        listMap.entrySet().forEach(entry -> {
            System.out.println(vertexes[index] + " ==> " + vertexes[entry.getKey()] + ":");
            List<int[]> paths = entry.getValue();

            AtomicInteger sum = new AtomicInteger(); // AtomicInteger是一个线程安全的具有原子性的能返回int类型的对象；

            paths.forEach(path -> {
                System.out.println("路径: " + vertexes[path[1]] + "==>" + vertexes[path[2]] + "\n路程: " + path[0] + "\n");
                sum.addAndGet(path[0]);
            });

            System.out.println("总路程：" + sum);

            System.out.println("----------------------------------------------------------");
        });
    }

    @Test
    public void testFloyd() {
        String[] vertexes = {"北京", "天津", "上海", "广州", "杭州", "武汉", "哈尔滨", "重庆", "成都"};

        int[][] edges = {{0, 1, 34}, {0, 2, 20}, {1, 2, 5}, {1, 3, 15},
                {1, 4, 50}, {2, 5, 50}, {3, 4, 40}, {4, 5, 20},
                {5, 7, 10}, {1, 5, 25}, {2, 6, 35}, {6, 7, 22},
                {7, 8, 11}, {2, 8, 6}};

        UndirectedGraph undirectedGraph = new UndirectedGraph(vertexes, edges);

        int[][] floyd = undirectedGraph.floyd();
        for (int i = 0; i < floyd.length; i++) {
            for (int j = 0; j < floyd[0].length; j++) {
                System.out.print(floyd[i][j] + "\t");
            }
            System.out.println();
        }
    }

}
